/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-sorted-array
   @Language: C++
   @Datetime: 16-02-09 04:52
   */

class Solution {
public:
	/**
	 * @param A: sorted integer array A which has m elements, 
	 *           but size of A is m+n
	 * @param B: sorted integer array B which has n elements
	 * @return: void
	 */
	/** Tips
	 * A has m elements but size is m+n, so merge A[0,m) and B[0,n)
	 * from end (m+n) to begin (0), which don't need another space
	 * sketch (default is ascending order)
	 * to be merged A: 2  3     6     8
	 * to be merged B: |  |  4  |  7  |  9
	 * after merge  A: 2  3  4  6  7  8  9
	 * */
	void mergeSortedArray(int A[], int m, int B[], int n) {
		// write your code here
		for(int l=m+n; l--; A[l]=A[m-1]>B[n-1]?A[--m]:B[--n]);
	}
};

// Method 2
class Solution {
public:
	/**
	 * @param A: sorted integer array A which has m elements, 
	 *           but size of A is m+n
	 * @param B: sorted integer array B which has n elements
	 * @return: void
	 */
	void mergeSortedArray(int A[], int m, int B[], int n) {
		// write your code here
		while(m+n!=m){
			if(m==0) A[m+n]=B[--n];
			else if(n==0) A[m+n]=A[--m];
			else A[m+n]=A[m-1]>B[n-1]?A[--m]:B[--n];
		}
	}
};
